#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

// EdgeNode类构造函数，初始化目标节点为0，链接指针为NULL
EdgeNode::EdgeNode()
{
    dest = 0;
    link = NULL;
}

// EdgeNode类构造函数，初始化目标节点和链表指针
EdgeNode::EdgeNode(int dest, EdgeNode *link)
{
    this->dest = dest;
    this->link = link;
}

// EdgeNode类析构函数，递归删除链表
EdgeNode::~EdgeNode()
{
    delete link;  // 删除链表中的所有节点
    link = NULL;  // 将链表指针置为NULL
}

// 获取目标节点的编号
int EdgeNode::getDest()
{
    return this->dest;
}

// 获取下一个边节点
EdgeNode *EdgeNode::getNext()
{
    return this->link;
}

// 设置目标节点的编号
void EdgeNode::setDest(int dest)
{
    this->dest = dest;
}

// 设置下一个边节点
void EdgeNode::setNext(EdgeNode *link)
{
    this->link = link;
}

// VertexNode类构造函数，初始化节点数据为'0'，边链表为空
VertexNode::VertexNode()
{
    this->data = '0';
    this->firstEdge = NULL;
}

// VertexNode类构造函数，初始化节点数据和边链表
VertexNode::VertexNode(char data, EdgeNode *firstEdge)
{
    this->data = data;
    this->firstEdge = firstEdge;
}

// VertexNode类析构函数，删除边链表
VertexNode::~VertexNode()
{
    delete this->firstEdge;  // 删除链表中的所有边节点
    this->firstEdge = NULL;  // 将边链表指针置为NULL
}

// 获取节点数据
char VertexNode::getData()
{
    return this->data;
}

// 获取节点的第一个边
EdgeNode *VertexNode::getFirstEdge()
{
    return this->firstEdge;
}

// 设置节点数据
void VertexNode::setData(char data)
{
    this->data = data;
}

// 设置节点的第一个边
void VertexNode::setFirstEdge(EdgeNode *firstEdge)
{
    this->firstEdge = firstEdge;
}

// MyGraph类构造函数，初始化图的节点数、边数，及VexList为空
MyGraph::MyGraph()
{
    nodeNum = edgeNum = 0;
    VexList = NULL;
}

// MyGraph类构造函数，使用给定的节点和边信息初始化图
MyGraph::MyGraph(int nodeNum, int edgeNum, char *nodeList, int *edgeStartList, int *edgeEndList)
{
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    this->VexList = new VertexNode[nodeNum];  // 为每个节点分配空间
    for (int i = 0; i < this->nodeNum; i++)
        this->VexList[i].setFirstEdge(NULL);  // 初始化每个节点的边链表为空
    for (int i = 0; i < this->nodeNum; i++)
    {
        this->VexList[i].setData(nodeList[i]);  // 设置节点数据
    }
    // 遍历所有边，构建边的链表
    for (int j = 0; j < this->edgeNum; j++)
    {
        // 从start节点到end节点的边
        EdgeNode *edge = new EdgeNode;
        edge->setDest(edgeEndList[j]);  // 设置目标节点
        edge->setNext(this->VexList[edgeStartList[j]].getFirstEdge());  // 将新边插入到边链表的头部
        this->VexList[edgeStartList[j]].setFirstEdge(edge);  // 更新起始节点的边链表

        // 从end节点到start节点的边（无向图）
        EdgeNode *edge2 = new EdgeNode;
        edge2->setDest(edgeStartList[j]);
        edge2->setNext(this->VexList[edgeEndList[j]].getFirstEdge());
        this->VexList[edgeEndList[j]].setFirstEdge(edge2);  // 更新目标节点的边链表
    }
}

// MyGraph类析构函数，删除节点列表和所有边链表
MyGraph::~MyGraph()
{
    delete[] this->VexList;  // 删除节点列表
    this->VexList = NULL;  // 将节点列表指针置为NULL
}

// 获取图的节点数
int MyGraph::getNodeNum()
{
    return this->nodeNum;
}

// 获取图的边数
int MyGraph::getEdgeNum()
{
    return this->edgeNum;
}

// 打印图的所有节点及其邻接节点
string MyGraph::printGraph()
{
    string result = "";
    // 遍历每个节点
    for (int i = 0; i < this->nodeNum; i++)
    {
        result += this->VexList[i].getData();  // 添加节点数据
        result += ": ";
        EdgeNode *p;
        p = this->VexList[i].getFirstEdge();
        // 遍历节点的边
        while (p != NULL)
        {
            result += this->VexList[p->getDest()].getData();  // 添加邻接节点的数据
            if (p->getNext() != NULL)
                result += " ";  // 如果还有下一个邻接节点，添加空格
            p = p->getNext();
        }
        if (i != this->nodeNum - 1)
            result += "\n";  // 添加换行符，除了最后一个节点
    }
    return result;
}

// 获取节点v的第一个未访问邻居节点
int MyGraph::getFirstNeighbor(int v, int *visited)
{
    if (this->VexList[v].getFirstEdge() != NULL)
        return this->VexList[v].getFirstEdge()->getDest();
    return -1;  // 如果没有邻接节点，返回-1
}

// 获取节点v与节点w之间的下一个未访问邻居节点
int MyGraph::getNextNeighbor(int v, int w, int *visited)
{
    EdgeNode *p = this->VexList[v].getFirstEdge();
    // 遍历v的边链表，找到w并返回w的下一个邻接节点
    while (p != NULL)
    {
        if (p->getDest() != w)
        {
            p = p->getNext();  // 如果当前节点不是w，继续遍历
        }
        else
        {
            p = p->getNext();  // 如果找到了w，继续遍历下一个邻接节点
            if (p != NULL)
                return p->getDest();  // 返回下一个邻接节点
            return -1;  // 如果没有下一个邻接节点，返回-1
        }
    }
    return -1;  // 如果没有找到w的邻接节点，返回-1
}

// 深度优先搜索（DFS）遍历图
void MyGraph::DFS(int v, int *visited, string &result)
{
    result += VexList[v].getData();  // 访问节点v
    result += " ";
    visited[v] = 1;  // 标记节点v为已访问
    int w = getFirstNeighbor(v, visited);
    // 遍历v的邻接节点
    while (w != -1)
    {
        if (!visited[w])  // 如果w未被访问
            DFS(w, visited, result);  // 递归访问w
        w = getNextNeighbor(v, w, visited);  // 获取v的下一个邻接节点
    }
}

// 对图进行深度优先搜索遍历
string MyGraph::graph_DFS_Traverse()
{
    string result;
    int *visited;
    visited = new int[this->nodeNum];  // 创建访问标记数组
    for (int i = 0; i < this->nodeNum; i++)
        visited[i] = 0;  // 初始化所有节点为未访问
    for (int i = 0; i < this->nodeNum; i++)
    {
        if (!visited[i])  // 如果节点i未被访问
            DFS(i, visited, result);  // 从节点i开始深度优先搜索
    }
    delete[] visited;  // 删除访问标记数组
    return result;
}

void MyGraph::BFS(int v, int *visited, string &result)
{
    result += VexList[v].getData();
    result += " ";
    visited[v] = 1;
    queue<int> q;
    q.push(v);
    while (!q.empty())
    {
        v = q.front();
        q.pop();
        int w = getFirstNeighbor(v, visited);
        while (w != -1)
        {
            if (!visited[w])
            {
                result += VexList[w].getData();
                result += " ";
                visited[w] = 1;
                q.push(w);
            }
            w = getNextNeighbor(v, w, visited);
        }
    }
}

string MyGraph::graph_BFS_Traverse()
{
    string result;
    int *visited;
    visited = new int[this->nodeNum];
    for (int i = 0; i < this->nodeNum; i++)
        visited[i] = 0;
    for (int i = 0; i < this->nodeNum; i++)
    {
        if (!visited[i])
            BFS(i, visited, result);
    }
    delete[] visited;
    return result;
}
